/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-10-17
 * Time: 20:15
 */
public class Solution1 {
    public int postbegin = 0;
    public TreeNode buildTree(String inorder, String postorder) {
        postbegin = postorder.length() - 1;
        return buildTreeChild(inorder, postorder, 0, inorder.length() - 1);
    }
    public TreeNode buildTreeChild(String  inorder,String postorder, int inbengin, int inend){
        //递归出口
        if (inbengin > inend) return null;
        //设置根节点
        TreeNode root = new TreeNode(postorder.charAt(postbegin));
        //在中序遍历中寻找根节点位置
        int rootpos = findPos(inorder,inbengin, inend,postorder.charAt(postbegin));
        postbegin--;
        //建立根节点的右子树和左子树
        root.right = buildTreeChild(inorder, postorder, rootpos + 1 ,inend);

        root.left = buildTreeChild(inorder, postorder, inbengin, rootpos - 1);
        return root;
    }
    //寻找根节点位置
    public int findPos(String inorder, int inbengin, int inend, int key){
        for (int i = inbengin; i <= inend; i++){
            if (inorder.charAt(i) == key){
                return i;
            }
        }
        return -1;
    }
}
